package hash;

import container.ContainerEmptyException;
import container.ContainerFullException;
import wrapper.Comparable;

public class ChainedScatterTable extends AbstractHashTable {
	protected Entry[] array;

	static final int nil = -1;

	public ChainedScatterTable(int length) {
		array = new Entry[length];
		for (int i = 0; i < length; ++i)
			array[i] = new Entry();
	}

	public int getLength() {
		return array.length;
	}

	public void purge() {
		for (int i = 0; i < getLength(); ++i)
			array[i].purge();
		count = 0;
	}

	protected static final class Entry {
		Comparable object;
		int next = nil;

		void purge() {
			object = null;
			next = nil;
		}
	}

	public void insert(Comparable object) {
		if (count == getLength())
			try {
				throw new ContainerFullException();
			} catch (ContainerFullException e) {
				// TODO Auto-generated catch block
				e.printStackTrace();
			}
		int probe = h(object);
		if (array[probe].object != null) {
			while (array[probe].next != nil)
				probe = array[probe].next;
			int tail = probe;
			probe = (probe + 1) % getLength();
			while (array[probe].object != null)
				probe = (probe + 1) % getLength();
			array[tail].next = probe;
		}
		array[probe].object = object;
		array[probe].next = nil;
		++count;
	}

	public Comparable find(Comparable object) {
		for (int probe = h(object); probe != nil; probe = array[probe].next) {
			if (object.isEQ(array[probe].object))
				return array[probe].object;
		}
		return null;
	}

	public void withdraw(Comparable object) {
		if (count == 0)
			try {
				throw new ContainerEmptyException();
			} catch (ContainerEmptyException e) {
				// TODO Auto-generated catch block
				e.printStackTrace();
			}
		int i = h(object);
		while (i != nil && object != array[i].object)
			i = array[i].next;
		if (i == nil)
			throw new IllegalArgumentException("obj not found");
		for (;;) {
			int j = array[i].next;
			while (j != nil) {
				int h = h(array[j].object);
				boolean contained = false;
				for (int k = array[i].next; k != array[j].next && !contained; k = array[k].next) {
					if (k == h)
						contained = true;
				}
				if (!contained)
					break;
				j = array[j].next;
			}
			if (j == nil)
				break;
			array[i].object = array[j].object;
			i = j;
		}
		array[i].object = null;
		array[i].next = nil;
		for (int j = (i + getLength() - 1) % getLength(); j != i; j = (j
				+ getLength() - 1)
				% getLength()) {
			if (array[j].next == i) {
				array[j].next = nil;
				break;
			}
		}
		--count;
	}
}
